package hot100.logos91To100;

/**
 * @author logos
 * date 2025/7/19 13:08
 * @version v1.0
 * @Package hot100.logos91To100
 */
public class logos100 {

    /**
     * 100. 寻找重复数
     * https://leetcode.cn/problems/find-the-duplicate-number/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int findDuplicate(int[] nums) {
            int n = nums.length;
            int fast = 0;
            int slow = 0;
            do {
                fast = nums[nums[fast]];
                slow = nums[slow];
            } while (fast != slow);
            fast = 0;
            while (fast != slow) {
                fast = nums[fast];
                slow = nums[slow];
            }
            return slow;
        }
    }
}
